package main

import (
	"fmt"
	"sort"
)

func main() {
	arr := []int{1211, 212134, 172, 966, 111}
    //BEGIN->离散化代码
	bak := make([]int, len(arr))
	copy(bak, arr)
	sort.Ints(bak)  //排序
    unique(&bak) //去重
	Len:=len(arr)
	myTree := InitTree(len(bak)-1)  //构建一个空的权值线段树
    for i:=0; i<Len; i++ {
        //END->离散化代码
		myTree.UpDate(lower_bound(bak, arr[i]), 1)  //二分查找arr[i] 在bak数组中的下标位置
    }
	fmt.Println(bak[myTree.Kth(3)]) //查找第3大
}

type node struct {
	sum, l, r int
	left, right *node
}

//动态开点函数，不需要建立空的线段树
func (root *node)insert(val int) {
	root.sum++
	if root.l == root.r {return}
	mid := (root.l + root.r) >> 1
	if val <= mid {
		if root.left == nil {root.left=&node{l: root.l, r: mid}}
		root.left.insert(val)
	} else {
		if root.right == nil {root.right=&node{l: mid+1, r: root.r}}
		root.right.insert(val)
	}
}

//初始化建立一个空树, 需要传入一个值域的最大值, 开辟空间建一个空的权值线段树
func InitTree(maxVal int) *node {
	tree := new(node)
	tree.buildTree(0, maxVal)
	return tree
}
func (this *node) buildTree(le, ri int) {
	this.l, this.r = le, ri
	if le == ri {return}
	mid := (le + ri) >> 1
	this.left, this.right = new(node), new(node)
	this.left.buildTree(le, mid)
	this.right.buildTree(mid+1, ri)
}

/*
	查询所有数的第k大值, 第k小值
	这是权值线段树的核心，思想如下(以第k大举例子):
	到每个节点时，如果右子树的总和大于等于k，说明第k 大值出现在右子树中，则递归进右子树；否则说明此时的第k 大值在左子树中，则递归进左子树	 注意：此时要将k 的值减去右子树的总和。
	如果我们要找的是第7 大值，右子树总和为4 ，7−4=3 ，说明在该节点的第7 大值在左子树中是第3 大值。
	最后一直递归到只有一个数时，那个数就是答案。
*/
func (this *node) Kth(k int) int {
	if this.l == this.r {return this.l}
	if k <= this.right.sum {return this.right.Kth(k)} else {
		return this.left.Kth(k-this.right.sum)
	}
}

//单点修改 (单个数出现的次数+1) x为更新哪个数, p=1 就是增加x -1就是删除x
func (this *node) UpDate(x, p int) {
	if this.l == this.r {this.sum += p; return}
	mid := (this.l + this.r) >> 1
	if x <= mid {this.left.UpDate(x, p)} else {this.right.UpDate(x, p)}
	this.sum = this.left.sum + this.right.sum
}

//查询整个值域区间查询某个数出现的次数
func (this *node) QueryCount(val int) int {
	if this.l == this.r {return this.sum}
	mid := (this.l + this.r) >> 1
	if val <= mid {return this.left.QueryCount(val)}
	if val > mid {return this.right.QueryCount(val)}
	return 0
}
//查询一个数的排名
func (this *node) QueryKth(val int) int {
    return this.QuerySpace(0, val-1) + 1
}
//查询一段值域区间出现的次数
func (this *node) QuerySpace(left, right int) int {
	if this.l == left && this.r == right {return this.sum}
	mid := (this.l + this.r) >> 1
	if right <= mid {return this.left.QuerySpace(left, right)} else if left > mid {
		return this.right.QuerySpace(left, right)} else {
			return this.left.QuerySpace(left, mid) + this.QuerySpace(mid+1, right)
	}
}

//离散化函数
//去重
func unique(arr *[]int) {
    slow, fast, Len := 0, 1, len(*arr)
    for fast < Len {
        if (*arr)[slow] != (*arr)[fast] {
            slow++
            (*arr)[slow] = (*arr)[fast]
        }
        fast++
    }
    *arr=(*arr)[:slow+1]
}

//二分
func lower_bound(arr []int, x int) int {
        left, right := 0, len(arr)-1
        for left <= right {
            mid := (right + left) >> 1
            if arr[mid] == x {
                return mid
            } else if arr[mid] > x {
                right = mid - 1
            } else {
                left = mid + 1
            }
        }
        return -1
}